/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 周斌
 * Date: 2024-05-17
 * Time: 17:44
 */
public class Main {
    //day10 贪心算法练习 力扣 55 跳跃游戏
    public boolean Jump1(int[] nums) {
        int left = 0;
        int  right = 0;
        int  maxPos = 0;
        int n = nums.length;
        // 防止跳不到最后一个位置，本质就是不能让right下标的值为0
        while (left <= right) {
            // 判断最右端位置是否可以跳到最后一个位置
            if (maxPos >= n - 1) {
                return true;
            }
            //更新位置
            for(int i = left; i <= right; i++) {
                maxPos = Math.max(maxPos,nums[i] + i);
            }
            left = right + 1;
            right = maxPos;
        }
        return false;
    }
    //day10 贪心算法练习 力扣 55 跳跃游戏二
    public int jump2(int[] nums) {
        int left = 0;
        int  right = 0;
        int  maxPos = 0;
        int n = nums.length;
        int ret = 0;
        // 防止跳不到最后一个位置，本质就是不能让right下标的值为0
        while (left <= right) {
            // 判断最右端位置是否可以跳到最后一个位置
            if (maxPos >= n - 1) {
                return ret;
            }
            //更新位置
            for(int i = left; i <= right; i++) {
                maxPos = Math.max(maxPos,nums[i] + i);
            }
            left = right + 1;
            right = maxPos;
            ret++;
        }
        return -1;
    }
}
